#include "BTreeNode.h"

using namespace std;

#define NULL_KEY -1
#define NULL_RID -1
#define NULL_PTR -1
#define PAGEFILE_SIZE PageFile::PAGE_SIZE

#define POINTER_SIZE sizeof(int)
#define KEY_SIZE sizeof(int)
#define TUPLE_SIZE (KEY_SIZE+2*sizeof(int))

//Minimum size: 4+4+(8*2)=24
#define MAX_NONLEAF_KEYS ((PAGEFILE_SIZE-(KEY_SIZE+POINTER_SIZE))/(KEY_SIZE+POINTER_SIZE))
//Minimum size: (12*2) + 4 + 4 = 32
#define MAX_LEAF_KEYS ((PAGEFILE_SIZE - (KEY_SIZE+POINTER_SIZE))/(sizeof(LEAF_NODE_TUPLE)))

struct LEAF_NODE_TUPLE{
		int key;
		RecordId rid;
};
struct NONLEAF_NODE_TUPLE{
		int key;
		PageId pid;
};



BTLeafNode::BTLeafNode(){
	LEAF_NODE_TUPLE * leaf_nodes = (LEAF_NODE_TUPLE *) &buffer[POINTER_SIZE+KEY_SIZE];
	int * firstNodes = (int *) &buffer[0];
	firstNodes[0] = 0; // size
	firstNodes[1] = NULL_PTR; //ptr to next node
	for(int i=0; i < MAX_LEAF_KEYS; i++)
	{
		leaf_nodes[i].key = NULL_KEY;
		leaf_nodes[i].rid.pid = NULL_PTR;
		leaf_nodes[i].rid.sid = NULL_PTR;
		
	}
	
	
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer);
	
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	
	int * leaf_nodes = (int *) &buffer[0];
	
	return leaf_nodes[0]; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int numKeys=getKeyCount();

	if(numKeys >= MAX_LEAF_KEYS){
		return RC_NODE_FULL;
	}
	else 
	{
		int keyIdx=0;
		LEAF_NODE_TUPLE * leaf_nodes = (LEAF_NODE_TUPLE *) &buffer[KEY_SIZE+ POINTER_SIZE];
		int * first_nodes = (int*) &buffer[0];
		
		for(int i=0; i <  numKeys; i++ )
		{
			//if the key is greater than the processor
			if(key >= leaf_nodes[i].key)
				keyIdx++;
			else
				break;
				
		}
		for( int i=numKeys; i > keyIdx; i-- )
		{
			leaf_nodes[i].key = leaf_nodes[i-1].key;
			leaf_nodes[i].rid = leaf_nodes[i-1].rid;
			
		}
		leaf_nodes[keyIdx].key = key;
		leaf_nodes[keyIdx].rid = rid;
		first_nodes[0]++;//increment size
		return 0;
	}
	 

}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey)
{ 
	int numKeys=getKeyCount();
	int keyIdx=0;
	int siblingKeyIdx = 0;
	siblingKey = -1;
	

	siblingKeyIdx = ((numKeys+1)/2);
	
	
	LEAF_NODE_TUPLE * leaf_nodes = (LEAF_NODE_TUPLE *) &buffer[KEY_SIZE+POINTER_SIZE];
	int * size = (int *) &buffer[0];
	
	for(int i=0; i <  numKeys; i++ )
	{
		//if the key is greater than the processor
		if(key >= leaf_nodes[i].key)
			keyIdx++;
		else
			break;
				
	}
	
	if(keyIdx > siblingKeyIdx)
	{
		//insert all keys to the right of siblingKey to sibling
		for( int i=siblingKeyIdx; i < numKeys; i++ )
		{
			sibling.insert(leaf_nodes[i].key, leaf_nodes[i].rid);
		}

		sibling.insert(key, rid);
		// update siblingKey
		siblingKey = leaf_nodes[siblingKeyIdx].key;

		//delete all copied keys from original node
		for(int i=siblingKeyIdx; i < numKeys; i++)
		{
			leaf_nodes[i].key = NULL_KEY;
			leaf_nodes[i].rid.sid = NULL_PTR;
			leaf_nodes[i].rid.pid = NULL_PTR;
			size[0]--;
		}
	}
	else if(keyIdx == siblingKeyIdx)
	{
		// update siblingKey
		siblingKey = key;

		for( int i=siblingKeyIdx; i < numKeys; i++ )
		{
			sibling.insert(leaf_nodes[i].key, leaf_nodes[i].rid);
		}

		// insert input key to sibling
		sibling.insert(key, rid);

		//delete all copied keys from original node
		for(int i=siblingKeyIdx; i < numKeys; i++)
		{
			leaf_nodes[i].key = NULL_KEY;
			leaf_nodes[i].rid.sid = NULL_PTR;
			leaf_nodes[i].rid.pid = NULL_PTR;
			size[0]--;
		}
	}
	else if(keyIdx < siblingKeyIdx)
	{
		for( int i=siblingKeyIdx-1; i < numKeys; i++ )
		{
			sibling.insert(leaf_nodes[i].key, leaf_nodes[i].rid);
		}

		// update siblingKey
		siblingKey = leaf_nodes[siblingKeyIdx-1].key;
		
		//delete all copied keys from original node
		for(int i=siblingKeyIdx-1; i < numKeys; i++)
		{
			leaf_nodes[i].key = NULL_KEY;
			leaf_nodes[i].rid.sid = NULL_PTR;
			leaf_nodes[i].rid.pid = NULL_PTR;
			size[0]--;
		}

		//correctly order the keys in the original node
		for( int i=siblingKeyIdx-1; i > keyIdx; i-- )
		{
			leaf_nodes[i].key = leaf_nodes[i-1].key;
			leaf_nodes[i].rid = leaf_nodes[i-1].rid;
		}

		leaf_nodes[keyIdx].key = key;
		leaf_nodes[keyIdx].rid = rid;
		size[0]++;

	}
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int rc;
	int numKeys = getKeyCount();
	LEAF_NODE_TUPLE * leaf_nodes = (LEAF_NODE_TUPLE *) &buffer[KEY_SIZE+POINTER_SIZE];
	rc=RC_NO_SUCH_RECORD;
	
	for(int i=0; i < numKeys ; i++){
		if(leaf_nodes[i].key >= searchKey){
			eid = i;	
			rc=0;
			return rc;
		}
	}
	return rc; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */

 
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	LEAF_NODE_TUPLE * nleaf_node =(LEAF_NODE_TUPLE *) &buffer[KEY_SIZE+POINTER_SIZE];
	
	if(eid < MAX_LEAF_KEYS){
		key = nleaf_node[eid].key;
		rid = nleaf_node[eid].rid;
		return 0;
	}
	else 
		return RC_NO_SUCH_RECORD;
	
}

void BTLeafNode::print(bool printAll){
	int MAX_SIZE= (printAll ? MAX_LEAF_KEYS : getKeyCount());
	
	LEAF_NODE_TUPLE * nleaf_node =(LEAF_NODE_TUPLE *) &buffer[POINTER_SIZE + KEY_SIZE];
	PageId * pid_nodes=(PageId *)&buffer[0];
	fprintf(stdout,"\n--------------------------\n");
	fprintf(stdout, "(S=%d) ", pid_nodes[0]);
	for(int i =0; i < MAX_SIZE; i++){
		fprintf(stdout,"%d ", nleaf_node[i].key);
		fprintf(stdout,"[%d, %d] ", nleaf_node[i].rid.sid, nleaf_node[i].rid.pid );
	}
	
	fprintf(stdout, "->%d ", pid_nodes[1]);
	fprintf(stdout,"\n--------------------------\n");
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId * nleaf_node =(PageId *) &buffer[0];
	
	return nleaf_node[1];
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{	
	PageId * nleaf_node =(PageId *) &buffer[0];
	nleaf_node[1]=pid;
	return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

BTNonLeafNode::BTNonLeafNode(PageId start)
{
	
	NONLEAF_NODE_TUPLE * nleaf_nodes = (NONLEAF_NODE_TUPLE *) &buffer[0];
	
	
	nleaf_nodes[0].key = 0;
	nleaf_nodes[0].pid = start;
	
	for(int i=1; i < MAX_NONLEAF_KEYS; i++)
	{
		nleaf_nodes[i].key = NULL_KEY;
		nleaf_nodes[i].pid = NULL_PTR;
		
	}
	
	
}

BTNonLeafNode::BTNonLeafNode()
{
	
	NONLEAF_NODE_TUPLE * nleaf_nodes = (NONLEAF_NODE_TUPLE *) &buffer[0];
	
	
	nleaf_nodes[0].key = 0;
	nleaf_nodes[0].pid = NULL_PTR;
	
	for(int i=1; i < MAX_NONLEAF_KEYS; i++)
	{
		nleaf_nodes[i].key = NULL_KEY;
		nleaf_nodes[i].pid = NULL_PTR;
		
	}
	
	
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	NONLEAF_NODE_TUPLE * nleaf_nodes = (NONLEAF_NODE_TUPLE *) &buffer[0];
	
	
	//the size
	return nleaf_nodes[0].key; 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	//TODO: fix insert
	int numKeys=getKeyCount();
	//fprintf(stdout, "getKeyCount: %d : %d (MAX)\n", numKeys, MAX_NONLEAF_KEYS);
	//print(true);
	if(numKeys >= MAX_NONLEAF_KEYS){
		return RC_NODE_FULL;
	}
	else 
	{
		int keyIdx=0;
		NONLEAF_NODE_TUPLE * nleaf_nodes = (NONLEAF_NODE_TUPLE *) &buffer[POINTER_SIZE + KEY_SIZE];
	
		for(int i=0; i <  (numKeys); i++ )
		{
			//if the key is greater than the processor
			if(key >= nleaf_nodes[i].key)
				keyIdx++;
			else
				break;
				
		}
		for( int i=numKeys; i > keyIdx; i-- )
		{
			nleaf_nodes[i].key = nleaf_nodes[i-1].key;
			nleaf_nodes[i].pid = nleaf_nodes[i-1].pid;
		}
		nleaf_nodes[keyIdx].key = key;
		nleaf_nodes[keyIdx].pid = pid;
		nleaf_nodes[-1].key += 1;
		return 0;
	}
	 

}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	int numKeys=getKeyCount();
	int keyIdx=0;
	int midKeyIdx = 0;
	
	midKey = -1;
	
	if( ((numKeys+1) % 2) == 1 )
	{
		midKeyIdx = ((numKeys+1)/2);
	}
	else
	{
		midKeyIdx = ((numKeys+1)/2) - 1;
	}
	
	
	NONLEAF_NODE_TUPLE * nleaf_nodes = (NONLEAF_NODE_TUPLE *) &buffer[POINTER_SIZE+KEY_SIZE];
	
	int * size = (int*) &buffer[0];

	midKey	 = nleaf_nodes[midKeyIdx].key;
	
	for(int i=0; i <  numKeys; i++ )
	{
		//if the key is greater than the processor
		if(key >= nleaf_nodes[i].key)
			keyIdx++;
		else
			break;
				
	}
	
	if(keyIdx > midKeyIdx)
	{
		//insert all keys to the right of midkey to sibling
		
		//siblingNode: (pid, midKey, midKey pid ....)
		
		//SARA ACHOUR
		sibling.initializeRoot(nleaf_nodes[midKeyIdx].pid,nleaf_nodes[midKeyIdx+1].key,nleaf_nodes[midKeyIdx+1].pid);
		
		for( int i=midKeyIdx+2; i < numKeys; i++ )
		{
			sibling.insert(nleaf_nodes[i].key, nleaf_nodes[i].pid);
		}

		sibling.insert(key, pid);
		// update midKey
		//midKey = nleaf_nodes[midKeyIdx].key;

		//delete all copied keys from original node
		for(int i=midKeyIdx; i < numKeys; i++)
		{
			nleaf_nodes[i].key = NULL_KEY;
			nleaf_nodes[i].pid = NULL_PTR;
			size[0]--;
		}
	}
	else if(keyIdx == midKeyIdx)
	{
		// update midKey
		midKey = key;
		//SARA ACHOUR
		sibling.initializeRoot(pid,nleaf_nodes[0].key,nleaf_nodes[0].pid);
		
		for( int i=midKeyIdx+1; i < numKeys; i++ )
		{
			sibling.insert(nleaf_nodes[i].key, nleaf_nodes[i].pid);
		}

		//delete all copied keys from original node
		for(int i=midKeyIdx; i < numKeys; i++)
		{
			nleaf_nodes[i].key = NULL_KEY;
			nleaf_nodes[i].pid = NULL_PTR;
			size[0]--;
		}
	}
	else if(keyIdx < midKeyIdx)
	{
		//SARA ACHOUR
		sibling.initializeRoot(nleaf_nodes[midKeyIdx].pid,nleaf_nodes[midKeyIdx+1].key,nleaf_nodes[midKeyIdx+1].pid);
		
		for( int i=midKeyIdx+2; i < numKeys; i++ )
		{
			sibling.insert(nleaf_nodes[i].key, nleaf_nodes[i].pid);
		}
		// update midKey SARA ACHOUR
		//midKey = nleaf_nodes[midKeyIdx-1].key;
		
		//delete all copied keys from original node
		for(int i=midKeyIdx; i < numKeys; i++)
		{
			nleaf_nodes[i].key = NULL_KEY;
			nleaf_nodes[i].pid = NULL_PTR;
			size[0]--;
		}

		insert(key, pid);

	}

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int rc;
	int numKeys = getKeyCount();
	NONLEAF_NODE_TUPLE * nleaf_nodes = (NONLEAF_NODE_TUPLE *) &buffer[POINTER_SIZE+KEY_SIZE];
	rc= RC_NO_SUCH_RECORD;
	
	pid = nleaf_nodes[-1].pid;
	for(int i=0; i < (numKeys) ; i++){
		if(nleaf_nodes[i].key <= searchKey)
		{
			pid = nleaf_nodes[i].pid;
			rc=0;
		}	
		
	}
	return rc; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	
	int * int_buffer = (int *) &buffer[0];
	int_buffer[0] = 1;
	int_buffer[1] = pid1;
	int_buffer[2] = key;
	int_buffer[3] = pid2;
	return 0; 
}

RC BTNonLeafNode::getPid(int idx, PageId& pid){
	if(idx >= getKeyCount()+1)
		return RC_INVALID_PID;
		
	NONLEAF_NODE_TUPLE * nleaf_node =(NONLEAF_NODE_TUPLE *) &buffer[KEY_SIZE+POINTER_SIZE];
	
	idx = idx-1;
	pid=nleaf_node[idx].pid;
	
	
	return 0;
}
void BTNonLeafNode::print(bool printAll){
	int MAX_SIZE= (printAll ? MAX_NONLEAF_KEYS : getKeyCount());
	NONLEAF_NODE_TUPLE * nleaf_node =(NONLEAF_NODE_TUPLE *) &buffer[KEY_SIZE+POINTER_SIZE];
	
	
	fprintf(stdout,"\n--------------------------\n");
	fprintf(stdout,"(S=%d) ", nleaf_node[-1].key);
	fprintf(stdout,"[%d] ", nleaf_node[-1].pid);
	for(int i =0; i < MAX_SIZE; i++){
		fprintf(stdout,"%d ", nleaf_node[i].key);
		fprintf(stdout,"[%d] ", nleaf_node[i].pid);
	}
	fprintf(stdout,"\n--------------------------\n");
}
